0%

Self-Learned Algorithms - 04

Posted on In

Self-Learned Algorithms - 04

This is my learning note about algorithms.

Reference

344.反转字符串

https://leetcode-cn.com/problems/reverse-string/

题解

  • 原地修改

解法

  • 双指针
1
2
3
4
5
i, j = 0, len(s)-1
while i < j:
  s[i], s[j] = s[j], s[i]
  i += 1
  j -= 1
  • 单指针？（奇怪的是时间没有减少，内存消耗反而增加了）
1
2
for i in range(len(s)//2):
	s[i], s[-(i+1)]= s[-(i+1)], s[i]
  • 一步法
1
s[:] = s[::-1]

s = A和s[:] = A的不同之处：s = A更改s这一变量名所指向的对象，让s变量指向A所指向的对象。s[:] = A对s指向的对象赋值，把A变量指向的对象的值逐个copy到s指向的对象中并覆盖s指向的对象的原来值。

387.字符串中的第一个唯一字符

https://leetcode-cn.com/problems

题解

  • 既然是第一个唯一字符，那就是倒着数最后一个出现第一次的字符。反向一次遍历，遇见出现第二次的就设置无限大，出现第一次的就保存位置指针，最后取最小值或-1即可。（萌新第一次灵光一现，也不知道之前有没有出现过这个思路）

解法

  • 两次遍历
1
2
3
4
5
6
7
dicts={}
for i in s:
	dicts[i]=dicts.get(i,0)+1
for i in range(len(s)):
  if dicts[s[i]]==1:
  	return i
return -1
  • 一次遍历？好像没有人用过这种解法？
1
2
3
4
5
6
7
8
9
if len(s) == 0: return -1

dicts={}
for i in range(len(s)-1, -1, -1):
  if s[i] not in dicts:
		dicts[s[i]] = i
  else:
    dicts[s[i]] = len(s) 
return -1 if min(dicts.values()) == len(s) else min(dicts.values())